Algorithm

Graph Coloring 是一種圖論中的應用問題，它通常用來解決如何為一個給定的圖中的每個節點分配一種顏色，使得相鄰的節點不具有相同的顏色的問題。

圖著色問題可以用來建模各種實際應用，例如在地圖上為不相鄰的地區分配顏色，以確保相鄰地區具有不同的顏色。這也可以應用於時間表排程問題、資源分配、無線通信中的頻譜分配等等。

使用 Backtracking 是從一個節點開始，依次為每個節點嘗試分配顏色，如果發現某個節點無法分配顏色，則回溯到前一個節點，嘗試其他顏色，一直進行下去，直到找到一種合法的著色方案，或者證明無解為止。

圖著色問題是一個 NP 困難問題，對於一些複雜的圖，可能需要高效的演算法來找到最佳的著色方案。

Code

class Graph(private val vertices: Int) {
    private val adjacencyMatrix = Array(vertices) { BooleanArray(vertices) }
    private val colors = IntArray(vertices)

    fun addEdge(v: Int, w: Int) {
        adjacencyMatrix[v][w] = true
        adjacencyMatrix[w][v] = true
    }

    fun graphColoring(): Boolean {
        return graphColoringUtil(0)
    }

    private fun graphColoringUtil(vertex: Int): Boolean {
        if (vertex == vertices) {
            return true
        }
        for (color in 1..vertices) {
            if (isSafe(vertex, color)) {
                colors[vertex] = color
                if (graphColoringUtil(vertex + 1)) {
                    return true
                }
                colors[vertex] = 0
            }
        }
        return false
    }

    private fun isSafe(vertex: Int, color: Int): Boolean {
        for (i in 0 until vertices) {
            if (adjacencyMatrix[vertex][i] && colors[i] == color) {
                return false
            }
        }
        return true
    }

    fun printSolution() {
        for (i in 0 until vertices) {
            println("Vertex $i: Color ${colors[i]}")
        }
    }
}

fun main() {
    val g = Graph(4)
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 2)
    g.addEdge(1, 3)

    if (g.graphColoring()) {
        println("Solution exists:")
        g.printSolution()
    } else {
        println("No solution exists")
    }
}

Graph(private val vertices: Int)

用於表示圖形，它包含了圖的鄰接矩陣、節點的顏色以及相關的方法。

addEdge(v: Int, w: Int)

函數用於在圖中添加邊，它將兩個節點之間的連接設置為 true。

graphColoring()

函數是圖著色的主函數。

它使用回溯法來遍歷圖中的每個節點，嘗試為每個節點分配一種顏色，同時檢查是否滿足著色的條件。

graphColoringUtil(vertex: Int)

函數是回溯法的輔助函數，它遞迴地嘗試為每個節點分配顏色，直到找到一個合法的著色方案或證明無解。

isSafe(vertex: Int, color: Int)

函數用於檢查給定節點是否可以安全地分配特定顏色，它檢查該節點的相鄰節點是否已經具有相同的顏色。

printSolution()

函數用於印出最終的著色方案。

此方法透過嘗試為每個節點找到一種不與相鄰節點相同的顏色，直到找到一個合法的著色方案或證明無解。

所有 Code 可以在 Github 找到 ～

感謝各位讀者，我們明天見！